template<u64 MAXN, u64 MAXS>
struct AhoCorasick {
    static constexpr int ALPHABEL = 26;

    int cnt;
    std::vector<int> end;
    std::vector<std::array<int, ALPHABEL>> tree;
    std::vector<int> fail;
    std::vector<bool> alert;
    std::vector<int> times;
    

    AhoCorasick() {
        end.assign(MAXN + 5, -1);
        tree.assign(MAXS + 5, {});
        fail.assign(MAXS + 5, 0);
        alert.assign(MAXS + 5, false);
        times.assign(MAXS + 5, 0);
        cnt = 0;
    }

    void add(int i, const std::string &s) {
        int u = 0;
        for(int j = 0, c; j < s.size(); j++) {
            c = s[j] - 'a';
            if(tree[u][c] == 0) {
                tree[u][c] = ++cnt;
            }
            u = tree[u][c];
        }
        end[i] = u;
        alert[u] = true;
    }

    void setfail() {
        std::queue<int> q;
        for(int i = 0; i < ALPHABEL; i++) {
            if(tree[0][i] > 0) {
                q.push(tree[0][i]);
            }
        }
        while(q.size()) {
            int u = q.front();
            q.pop();

            for(int i = 0; i < ALPHABEL; i++) {
                if(tree[u][i] == 0) {
                    tree[u][i] = tree[fail[u]][i];
                } else {
                    fail[tree[u][i]] = tree[fail[u]][i];
                    q.push(tree[u][i]);
                }
            }

            if(alert[fail[u]]) {
                alert[u] = true;
            }
        }
    }

    template<bool Counter = true>
    void work() {
        setfail();
        if(Counter) {
            std::string s;
            std::cin >> s;

            for(int i = 0, u = 0; i < s.size(); i++) {
                u = tree[u][s[i] - 'a'];
                times[u]++;
            }

            std::vector<std::vector<int>> g(MAXS + 5);

            auto add_Edge = [&](int u, int v) -> void {
                g[u].push_back(v);
            };

            auto dfs = [&] (auto &&self, int u) -> void {
                for(auto v : g[u]) {
                    self(self, v);
                    times[u] += times[v];
                }
            };

            for(int i = 1; i <= cnt; i++) {

                add_Edge(fail[i], i);
            }

            dfs(dfs, 0);
        }
    }

    int get_index_i_times(int i) {
        return times[end[i]];
    }

};